package problem.imo09_6;
import java.util.ArrayList;
import java.util.Arrays;

class Jumper {
	public static ArrayList<int[]> findSafeHops(int[] hops, int[] traps) {
		if (contains(traps, sum(hops))) {
			return null;
		}
        int hopsLen = hops.length;
		ArrayList<int[]> safeHops = new ArrayList<int[]>();
        if (hopsLen == 1) {
		    safeHops.add(hops);
			return safeHops;
		}
		ArrayList<int[]> subSolutions;
		for (int i = 0; i < hopsLen; i++) {
            subSolutions = findSafeHops(subArray(hops,i),traps);
            if (subSolutions != null) {
                for (int[] subHops : subSolutions) {
                    int[] fullHops = new int[hopsLen];
                    System.arraycopy(subHops, 0, fullHops, 0, hopsLen - 1);
                    fullHops[hopsLen - 1] = hops[i];
                    safeHops.add(fullHops);
                }
            }
		}
		return safeHops;
	}
	private static int sum(int[] arr) {
		int s = 0;
		for (int i : arr) {
			s += i;
		}
		return s;
	}
	private static int[] subArray(int[] arr, int excludeIndex) {
		int len = arr.length;
		int[] newArr = new int[len - 1];
		for (int i = 0; i < excludeIndex; i++) {
			newArr[i] = arr[i];
		}
		for (int i = excludeIndex + 1; i < len; i++) {
			newArr[i - 1] = arr[i];
		}
		return newArr;
	}

	private static boolean contains(int[] arr, int e) {
        for (int i : arr) {
			if (i == e)
				return true;
		}
		return false;
	}
	private static boolean trapped(int[] hops, int trap) {
		int s = 0;
		for (int i : hops) {
			s += i;
			if (s == trap)
				return true;
			if (s > trap)
				return false;
		}
		return false;
	}
    private static boolean trapped(int[] hops, int[] traps) {
		for(int trap : traps){
            if(trapped(hops,trap))
                return true;
        }
		return false;
	}
	public static void main(String[] args) {
		int[] hops = {1,2,3,4,5,6,7,9,10};
		int[] traps = {14,10,15,21,24,27,31,44};
		ArrayList<int[]> solutions = findSafeHops(hops, traps);
		if (solutions != null) {
			/*for (int[] solution : solutions) {
				for (int i : solution) {
					System.out.print(i + " ");
				}
				System.out.println("");
			} */
			System.out.println("There are " + solutions.size() + " solutions.");
            for(int[] solution : solutions){
                if(trapped(solution,traps)){
                    System.out.println("but failed!!");
                    break;
                }
            }
		}
		else{
			System.out.println("No safe hops available!");
		}
	}
}
